home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 16 / CU Amiga Magazine's Super CD-ROM 16 (1997-10-16)(EMAP Images)(GB)[!][issue 1997-11].iso / CUCD / Graphics / Ghostscript / source / dstack.h < prev    next >
Text File  |  1997-01-19  |  11KB  |  280 lines
  1. /* Copyright (C) 1992, 1996, 1997 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* dstack.h */
  20. /* Definitions for the dictionary stack */
  21. #include "istack.h"
  22.  
  23. /* Define the dictionary stack and systemdict. */
  24. extern ref_stack d_stack;
  25. extern ref ref_systemdict;
  26. #define systemdict (&ref_systemdict)
  27.  
  28. /* Define the dictionary stack pointers. */
  29. typedef s_ptr ds_ptr;
  30. typedef const_s_ptr const_ds_ptr;
  31. #define dsbot (d_stack.bot)
  32. #define dsp (d_stack.p)
  33. #define dstop (d_stack.top)
  34.  
  35. /* Macro to ensure enough room on the dictionary stack */
  36. #define check_dstack(n)\
  37.   if ( dstop - dsp < (n) )\
  38.     { d_stack.requested = (n); return_error(e_dictstackoverflow); }
  39.  
  40. /* Check whether a dictionary is one of the permanent ones on the d-stack. */
  41. bool dict_is_permanent_on_dstack(P1(const ref *));
  42.  
  43. /*
  44.  * Switching between Level 1 and Level 2 involves inserting and removing
  45.  * globaldict on the dictionary stack.  Instead of truly inserting and
  46.  * removing entries, we replace globaldict by a copy of systemdict in
  47.  * Level 1 mode.  min_dstack_size, the minimum number of entries, does not
  48.  * change depending on language level; the countdictstack and dictstack
  49.  * operators must take this into account.
  50.  */
  51. extern uint min_dstack_size;
  52.  
  53. /*
  54.  * The dictionary stack is implemented as a linked list of blocks;
  55.  * operators that access the entire d-stack must take this into account.
  56.  * These are:
  57.  *    countdictstack  dictstack
  58.  * In addition, name lookup requires searching the entire stack, not just
  59.  * the top block, and the underflow check for the dictionary stack
  60.  * (`end' operator) is not just a check for underflowing the top block.
  61.  */
  62.  
  63. /*
  64.  * Cache a value for fast checking of def operations.
  65.  * If the top entry on the dictionary stack is a writable dictionary,
  66.  * dsspace is the space of the dictionary; if it is a non-writable
  67.  * dictionary, dsspace = -1.  Then def is legal precisely if
  68.  * r_space(pvalue) <= dsspace.  Note that in order for this trick to work,
  69.  * the result of r_space must be a signed integer; some compilers treat
  70.  * enums as unsigned, probably in violation of the ANSI standard.
  71.  */
  72. extern int dsspace;
  73. #define dtop_can_store(pvalue) ((int)r_space(pvalue) <= dsspace)
  74. /*
  75.  * Cache values for fast name lookup.  If the top entry on the dictionary
  76.  * stack is a readable dictionary with packed keys, dtop_keys, dtop_npairs,
  77.  * and dtop_values are keys.value.packed, npairs, and values.value.refs
  78.  * for that dictionary; otherwise, these variables point to a dummy
  79.  * empty dictionary.
  80.  */
  81. extern const ref_packed *dtop_keys;
  82. extern uint dtop_npairs;
  83. extern ref *dtop_values;
  84. /*
  85.  * Reset the cached top values.  Every routine that alters the
  86.  * dictionary stack (including changing the protection or size of the
  87.  * top dictionary on the stack) must call this.
  88.  */
  89. void dict_set_top(P0());
  90.  
  91. /*
  92.  * Define a special fast entry for name lookup in the interpreter.
  93.  * The key is known to be a name; search the entire dict stack.
  94.  * Return the pointer to the value slot.
  95.  * If the name isn't found, just return 0.
  96.  */
  97. ref *dict_find_name_by_index(P1(uint nidx));
  98. #define dict_find_name(pnref) dict_find_name_by_index(name_index(pnref))
  99.  
  100. /* Define the hashing function for names. */
  101. /* We don't have to scramble the index, because */
  102. /* indices are assigned in a scattered order (see name_ref in iname.c). */
  103. #define dict_name_index_hash(nidx) (nidx)
  104.  
  105. /*
  106.  * Define an extra-fast macro for name lookup, optimized for
  107.  * a single-probe lookup in the top dictionary on the stack.
  108.  * Amazingly enough, this seems to hit over 90% of the time
  109.  * (aside from operators, of course, which are handled either with
  110.  * the special cache pointer or with 'bind').
  111.  */
  112. #define dict_find_name_by_index_inline(nidx,htemp)\
  113.   (dtop_keys[htemp = dict_hash_mod_inline(dict_name_index_hash(nidx),\
  114.      dtop_npairs) + 1] == pt_tag(pt_literal_name) + (nidx) ?\
  115.    dtop_values + htemp : dict_find_name_by_index(nidx))
  116. /*
  117.  * Define a similar macro that only checks the top dictionary on the stack.
  118.  */
  119. #define if_dict_find_name_by_index_top(nidx,htemp,pvslot)\
  120.   if ( ((dtop_keys[htemp = dict_hash_mod_inline(dict_name_index_hash(nidx),\
  121.      dtop_npairs) + 1] == pt_tag(pt_literal_name) + (nidx)) ?\
  122.     ((pvslot) = dtop_values + (htemp), 1) :\
  123.     0)\
  124.      ) 
  125.  
  126. /*
  127. Notes on dictionary lookup performance
  128. --------------------------------------
  129.  
  130. We mark heavily used operations with a * below; moderately heavily used
  131. operations with a +.
  132.  
  133. The following operations change the dictionary stack:
  134.     +begin, +end
  135.     readonly (on a dictionary that is on the stack)
  136.     noaccess (on a dictionary that is on the stack)
  137. We implement cleardictstack as a series of ends.
  138.  
  139. The following operations change the contents of dictionaries:
  140.     *def, +put
  141.     undef
  142.     restore
  143.     .setmaxlength
  144. We implement store in PostScript, and copy as a series of puts.  Many
  145. other operators also do puts (e.g., ScaleMatrix in makefont,
  146. Implementation in makepattern, ...).  Note that put can do an implicit
  147. .setmaxlength (if it has to grow the dictionary).
  148.  
  149. The following operations look up keys on the dictionary stack:
  150.     *(interpreter name lookup)
  151.     load
  152.     where
  153.  
  154. Current design
  155. --------------
  156.  
  157. Each name has a pointer that has one of 3 states:
  158.     - This name has no definitions.
  159.     - This name has exactly one definition, in systemdict or userdict.
  160.     In this case, the pointer points to the value slot.
  161.     - This name has some other status.
  162.  
  163. We cache some pointers to the top dictionary on the stack if it is a
  164. readable dictionary with packed keys, which allows us to do fast,
  165. single-probe lookups in this dictionary.  We also cache a value that
  166. allows us to do a fast check for stores into the top dictionary
  167. (writability + space check).
  168.  
  169. Full shallow binding
  170. --------------------
  171.  
  172. We implement shallow binding with a pointer in each name that points to
  173. the value slot that holds the name's definition.  If the name is
  174. undefined, or if we don't know where the slot is, the binding pointer
  175. points to a ref with a special type t__invalid, which cannot occur
  176. anywhere else.  "Clearing" the pointer means setting it to point to this
  177. ref.
  178.  
  179. We also maintain a pair of pointers that bracket the value region of the
  180. top dictionary on the stack, for fast checking in def.  If the top
  181. dictionary is readonly or noaccess, the pointers designate an empty area.
  182. We call this the "def region" cache.
  183.  
  184. We implement the above operations as follows:
  185.     begin - push the dictionary on the stack; set the pointers of
  186.         all name keys to point to the corresponding value slots.
  187.     end - pop the stack; clear the pointers of all name keys.
  188.     readonly - if the dictionary is the top one on the stack,
  189.         reset the def region cache.
  190.     noaccess - clear the pointers of all name keys.  (This is overly
  191.         conservative, but this is a very rare operation.)
  192.         Also reset the def region cache if the dictionary is
  193.         the top one on the stack.
  194.     def - if the key is a name and its pointer points within the cached
  195.         def region, store the value through the pointer; otherwise,
  196.         look up the key in the top dictionary, store the value,
  197.         and if the key is a name, set its pointer to the value slot.
  198.     put - if the key is a name and wasn't in the dictionary before,
  199.         clear its pointer.  (Conservative, but rare.)
  200.     undef - if the key is a name, clear its pointer.  (Overly
  201.         conservative, but rare.)
  202.     restore - if either the old or the new value of a change is a name
  203.         (possibly in a packed array), clear its pointer.  This is
  204.         conservative, but easy to detect, and probably not *too*
  205.         conservative.
  206.     .setmaxlength - clear all the pointers, like noaccess.
  207.     (name lookup) - fetch the value through the pointer and dispatch
  208.         on its type; if the type is t__invalid, do a full search
  209.         and set the pointer.  This avoids a separate check for a
  210.         clear pointer in the usual case where the pointer is valid.
  211.     load - if the pointer is clear, do a search and set the pointer;
  212.         then fetch the value.
  213.     where - always do a full search and set the pointer.
  214.         (Conservative, but rare.)
  215.  
  216. One place where shallow binding will result in major new overhead is the
  217. extra push of systemdict for loading fonts.  This probably isn't a problem
  218. in real life.
  219.  
  220. Adaptive shallow binding
  221. ------------------------
  222.  
  223. We do validity checking for the name value cache using an epoch counter.
  224. For each dictionary D, we keep an on-stack flag F.  Each dictionary stack
  225. entry is <D,M,F,E> where D is the actual dictionary, M is a mark vector of
  226. V bits (V is a system constant, probably 64), F is D's former on-stack
  227. flag, and E is the epoch at which the entry was made.  For each name K, we
  228. keep a cache <P,E> where P is a pointer to the dictionary value slot that
  229. holds the current value of K, and E is an epoch value; the cache is valid
  230. if K->E >= dsp->E.  Here is what happens for each operation:
  231.  
  232. ****** Still need to handle names defined only in systemdict or userdict?
  233.  
  234. To initialize:
  235.     Epoch = 0
  236. To clear the cache entry for K:
  237.     *K = <ptr to invalid value, 0>
  238. begin(D):
  239.     *++dsp = <D, {0...}, D->F, ++Epoch>
  240.     set D->F
  241. value = lookup(K):
  242.     if K->E >= dsp->E
  243.       value = *K->P
  244.     else
  245.       do lookup as usual
  246.       *K = <ptr to value, Epoch>
  247.       set dp->M[i mod V] where dp is the dstack slot of the dictionary
  248.         where K was found and i is the index within that dictionary
  249. end:
  250.     for each i such that dsp->M[i] is set,
  251.       clear the cache entry for dsp->D->keys[i, i+V, ...]
  252.     dsp->D->F = dsp->F
  253.     --dsp
  254. noaccess(D):
  255.     if D->F is set,
  256.       clear the cache entries for all name keys of D
  257. readonly(D):
  258.     << nothing >>
  259. .setmaxlength(D,N):
  260.     same as noaccess
  261. restore:
  262.     If either the old or the new value of a change is a name
  263.       (possibly in a packed array), clear its cache entry.  This is
  264.       conservative, but easy to detect, and probably not *too*
  265.       conservative.
  266. def(K,V):
  267.     if K->P points into dsp->D
  268.       *K->P = V
  269.     else
  270.       put the new value in dsp->D
  271.       set *K and dsp->M[i mod V] as for a lookup
  272. put(D,K,V):
  273.     if K is already defined in D, do nothing special
  274.     otherwise, if D->F isn't set, do nothing special
  275.     otherwise, clear K's cache entry
  276. undef(D,K):
  277.     if D->F is set,
  278.       clear K's cache entry
  279. */
  280.